Synchronization objects, such as locks or semaphores, are used within computing systems to control access to shared resources, such as data structures. One example type of data structure, referred to as hash tables, is generally used to provide a unique mapping between a set of input values, referred to as key values, and storage locations for corresponding output values, referred to as buckets. Hash tables are used in various contexts, such as, database applications, implementing data structures such as associative arrays and sets, memory caches, networking applications, or other situations in which a unique mapping between input values and output values is desirable.
One technique to increase the speed of hash tables is to provide a hardware-based hash table. When a hash table is implemented in hardware, the hash table may perform one or more operations concurrently on multiple “buckets” or portions of the hash table. Thus, multiple processes and/or threads may request access to the hash table to insert, delete or look up data in the hash table. If, for example, multiple threads attempt to simultaneously modify data stored in a bucket of the hash table, the data may become inconsistent or deadlock may occur between the threads. In such cases, synchronization object, e.g., a locks, may be associated with the buckets of the hash table to avoid deadlock and ensure data consistency. A lock restricts access to a resource such as a bucket in a hash table by allowing only a single thread at a point in time to modify data in the bucket. In many cases, multiple threads may each request multiple buckets in a hash table. Multiple buckets may also be locked within a hash table a point in time as multiple operations are performed simultaneously on the hash table. As the number of requests increase for locks of multiple buckets, trade-offs may occur between performance, fairness, and data integrity.
In the past, only a single software resource was able to write to a data structure such as a hash table at a point in time. This property preserved integrity and coherence of the data stored within the hash table. In multithreaded and multiprocess environments, synchronization objects such as locks were used to ensure that only a single thread or process was able to write to the hash table at a point in time. For example, when a lock was obtained by a thread, no other threads could perform insert or delete operations on the hash table. Consequently, all other processes and threads were “blocked” and therefore were required to wait until the lock was released before performing insert or delete operations. When the lock was released, another thread would acquire the lock and perform one or more operations on the hash table. In this way, only a single thread or process could modify the hash table.